package lib

//link to 1094
func init() {
	Probs = append(Probs, Problem{
		Num:         370,
		Discription: "每次操作在数组[i,j]范围内+一个值，所有操作完成后的数组值",
		Level:       2,
		Labels: map[string]int{
			"差分数组": 1,
			"前缀和":  1,
		},
	})
}

//差分数组的思想：将连续范围内的修改优化成 2 * O（1）
//diff[i]=res[i]-res[i-1],diff[0]=res[0]
//res[i]=diff[0]+diff[1]+..diff[i]
func GetModifiedArray(length int, updates [][]int) []int {
	diff := make([]int, length+1)
	for i := range updates {
		diff[updates[i][0]] += updates[i][2]
		diff[updates[i][1]+1] -= updates[i][2]
	}

	res := make([]int, length)
	res[0] = diff[0]
	for i := 1; i < length; i++ {
		res[i] = res[i-1] + diff[i]
	}

	return res
}
